package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.HashSet;
import java.util.Set;

/**
 * 描述：快慢指针？？？？？？？？？？？
 * 当快指针与慢指针相遇 再从起点出发一个指针 此指针一定会与慢指针在入口点相遇
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-04 09:27
 */
public class BM22链表中环的入口节点 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        listNode.next = listNode2;
        listNode2.next = listNode;

        System.out.println(detectCycle(listNode));
    }


    /**
     * 怎么判断入环的节点
     *
     * 使用set 当碰到无法插入的节点即代表入环节点
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {

        Set<ListNode> set = new HashSet<>();

        while (head != null &&head.next != null){
            if(!set.add(head)){
                return head;
            }
            head = head.next;
        }
        return null;
    }






    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next.getClass().getName() +
                    '}';
        }
    }
}
